/**
 * time: 2022.12.16
 * 
*/
#include<stdio.h>
#define LEN 15 // 15个学生

// 学生结构体
typedef struct {
    char id[11];    // 学号
    char name[8];   // 姓名
    int birth;      // 生日, 格式 20221216
    int birthPlace; // 省内0省外1
    double score;   // C语言成绩
}student;

student stu[LEN] = {
    {"2210010101", "jike1", 20030120, 0, 80},
    {"2210010102", "jike2", 20030210, 1, 78},
    {"2210010103", "jike3", 20031222, 0, 89},
    {"2210010104", "jike4", 20030915, 0, 76},
    {"2210010105", "jike5", 20030822, 1, 71},
    {"2210010106", "jike6", 20030610, 1, 84},
    {"2210010107", "jike7", 20031213, 0, 87},
    {"2210010108", "jike8", 20031119, 1, 88},
    {"2210010109", "jike9", 20030407, 1, 73},
    {"2210010110", "jike10", 20030710, 0, 85},
    {"2210010111", "jike11", 20030519, 0, 82},
    {"2210010112", "jike12", 20030320, 0, 72},
    {"2210010113", "jike13", 20030423, 1, 74},
    {"2210010114", "jike14", 20030919, 0, 75},
    {"2210010115", "jike15", 20031204, 1, 90},
} ;

student CopyInfo(student src); // 辅助
student scoreMax(const student arr[]);
double getAverage(student arr[], int place);
double getVariance(student arr[], int place);

void DirectInsertSort(student arr[]); // 可选
void BinaryInsertSort(student arr[]); 

int main(){
    student a;

    puts("\nsolve 1: 输出成绩最高的学生信息");
    a = scoreMax(stu);
    printf("%-12s%-8s%-10d%-5d%.lf\n", a.id, a.name, a.birth, a.birthPlace, a.score);

    puts("\nsolve 2: C语言成绩的平均值和方差");
    printf("区内学生 平均值=%5.2lf 方差=%5.2lf\n区外学生 平均值=%5.2lf 方差=%5.2lf\n", 
        getAverage(stu, 0), getVariance(stu, 0),
        getAverage(stu, 1), getVariance(stu, 1));

    puts("\nsolve 3: 按生日先后排序输出全部学生的信息");
    //DirectInsertSort(stu); // 最简单的查找, 不推荐
    BinaryInsertSort(stu);
    for (int i = 0; i < LEN; i++) {
        printf("%-12s%-8s%-10d%-5d%.lf\n", 
            stu[i].id, stu[i].name, stu[i].birth, stu[i].birthPlace, stu[i].score);
    }

    getchar();
    return 0;
}

// 功能: 复制学生对象, 返回结构体类型
student CopyInfo(student src) {
    student a; 
    char *p = a.id, *q = src.id;
    while (*p++ = *q++);
    p = a.name, q = src.name;
    while (*p++ = *q++);

    a.birth = src.birth;
    a.birthPlace = src.birthPlace;
    a.score = src.score;
    return a;
}

// 功能: 查找C语言成绩最高的学生, 获取其学号
student scoreMax(const student arr[]) {
    student max = arr[0];
    int i;
    for (i = 1; i < LEN; i++) {
        if (max.score < arr[i].score)
            max = CopyInfo(arr[i]); 
    }
    return max;
}

// 功能: 求平均值, 参数为分区
double getAverage(student arr[], int place) {
    double sum = 0.0;   // 平均值之和
    int count = 0;      // 统计省内或省外人数
    int i;
    for (i = 0; i < LEN; ++i) {
        if (arr[i].birthPlace == place) {
            sum += arr[i].score;
            count++;
        }
    }
    return (sum / count);
}

// 功能: 求方差, 参数为分区
double getVariance(student arr[], int place) {
    double sum = 0.0; // 方差之和
    int count = 0;    // 统计省内或省外人数
    double ave = getAverage(arr, place);
    int i;
    for (i = 0; i < LEN; ++i) {
        if (arr[i].birthPlace == place) {
            sum += (arr[i].score - ave) * (arr[i].score - ave);
            count++;
        }
    }
    return (sum / count);
}

// 功能: 直接插入排序, 使数组元素递增
void DirectInsertSort(student arr[]) {
    student x; // 待插
    int i, j;
    // 从第2个开始, 左侧当作有序, 右侧无序
    for (i = 1; i < LEN; i++) {
        if (arr[i].birth < arr[i-1].birth) {
            x = CopyInfo(arr[i]);
            // 从后往前依次查找左侧, 每个元素后移1位, 直到找到正确位置
            for (j = i - 1; j > -1; j--) {
                if (x.birth > arr[j].birth)
                    break;
                arr[j + 1] = CopyInfo(arr[j]);
            }
            arr[j+1] = CopyInfo(x); 
        }
    }
}

// 功能: 折半插入排序
// 逻辑: 对左侧的有序部分利用二分法查找要插入的位置
void BinaryInsertSort(student arr[]) {
    student x;
    int low, high, mid;
    int i, j;
    for (i = 1; i < LEN; i++) {
        low = 0;
        high = i - 1;
        for (; low <= high;) {
            mid = low + (high - low) / 2;
            if (arr[i].birth < arr[mid].birth)
                high = mid - 1;
            else
                low = mid + 1;
        }
        
        if (high == i - 1) continue; // high没变时不需要调整位置, 直接跳过

        x = CopyInfo(arr[i]);
        // 对有序部分, 插入位置后面的每个元素后移1位
        for (j = i - 1; j > high; --j) {
            arr[j + 1] = CopyInfo(arr[j]); 
        }
        arr[high + 1] = CopyInfo(x);
    }
}